package com.demo.jzoffer2;

import org.junit.Test;

/**
 * @author gy
 * @date 2023/03
 */
public class Test0323_01 {

    /**
     * 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，
     * 其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
     *
     * 输入: [1,2,3,4,5]
     * 输出: [120,60,40,30,24]
     *
     * 所有元素乘积之和不会溢出 32 位整数
     * a.length <= 100000
     *
     * 思路分析：
     * 其实本质上就是两个dp数组，分别维护了 i 左侧 和 i 右侧的乘积和。
     *
     * i 0 1 2 3 4
     * a 1 2 3 4 5
     *
     * b0 = 1
     * b1 = b0 * a0 = a0 -> b0 * a0
     * b2 = b1 * a1 = (a0) * a1 -> b1 * a1
     * b3 = b2 * a2 = (a0 * a1) * a2 -> b2 * a2
     * b4 = b3 * a3 = (a0 * a1 * a2) * a3 -> b3 * a3
     *
     * 直接复用上次计算，降低时间复杂度
     * @param a
     * @return
     */
    public int[] constructArr(int[] a) {
        // 特例处理
        if (a == null || a.length == 0){
            return a;
        }
        // 初始化
        int len = a.length;
        int[] left = new int[len]; // i 左侧的乘积
        int[] right = new int[len]; // i 右侧的乘积
        int[] res = new int[len]; // 返回结果，left[i] * right[i]

        left[0] = 1; // 左侧乘积初始值
        for (int i = 1; i < len; i++) {
            left[i] = left[i - 1] * a[i - 1];
        }

        right[len - 1] = 1; // 右侧乘积初始值
        for (int i = len - 2; i >= 0; i--) {
            right[i] = right[i + 1] * a[i + 1];
        }
        // 返回乘积数组
        for (int i = 0; i < len; i++) {
            res[i] = left[i] * right[i];
        }

        return res;
    }


    @Test
    public void m1() {

    }

    @Test
    public void m2() {

    }

    @Test
    public void m3() {

    }

}
